/*
https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/
2246. 相邻字符不同的最长路径
方钊堉 2024.11.6
dfs
*/

class Solution {
public:
    int dfs(int currentNode, int& maxLength, string& labels, vector<vector<int>>& children) {
        int currentLength = 1; // 当前节点的路径长度
        pair<int, int> longestPaths = {0, 0}; // 存储两个最长路径长度
        // 遍历当前节点的所有子节点
        for (int nextNode : children[currentNode]) {
            if (labels[currentNode] == labels[nextNode]) {
                // 如果当前节点和子节点的标签相同，递归处理子节点
                dfs(nextNode, maxLength, labels, children);
                continue;
            }
            int subPathLength = dfs(nextNode, maxLength, labels, children);

            // 更新最长路径
            if (subPathLength >= longestPaths.first) {
                longestPaths.second = longestPaths.first;
                longestPaths.first = subPathLength;
            } else if (subPathLength > longestPaths.second) {
                longestPaths.second = subPathLength;
            }
        }
        // 更新全局最长路径
        maxLength = max(maxLength, 1 + longestPaths.first + longestPaths.second);
        return 1 + longestPaths.first;
    }
    int longestPath(vector<int>& parents, string labels) {
        int size = parents.size();
        vector<vector<int>> children(size); // 存储每个节点的子节点

        // 构建树的邻接表
        for (int i = 0; i < size; ++i) {
            int from = parents[i];
            int to = i;
            if (from == -1) {
                continue; // 根节点跳过
            }
            children[from].push_back(to);
        }

        int maxLength = 0; // 存储最长路径长度
        dfs(0, maxLength, labels, children); // 从根节点开始深度优先搜索
        return maxLength;
    }
};